|
:''Boolean algebras have been formally defined variously as a kind of lattice and as a kind of ring. This article presents them, equally formally, as simply the models of the equational theory of two values, and observes the equivalence of both the lattice and ring definitions to this more elementary one.'' Boolean algebra is a mathematically rich branch of abstract algebra. Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1 (whose interpretation need not be numerical). Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under zero or more operations satisfying certain equations. Just as there are basic examples of groups, such as the group Z of integers and the permutation group ''S''''n'' of permutations of ''n'' objects, there are also basic examples of Boolean algebra such as the following. *The algebra of binary digits or bits 0 and 1 under the logical operations including disjunction, conjunction, and negation. Applications include the propositional calculus and the theory of digital circuits. *The algebra of sets under the set operations including union, intersection, and complement. Applications include any area of mathematics for which sets form a natural foundation. Boolean algebra thus permits applying the methods of abstract algebra to mathematical logic, digital logic, and the set-theoretic foundations of mathematics. Unlike groups of finite order, which exhibit complexity and diversity and whose first-order theory is decidable only in special cases, all finite Boolean algebras share the same theorems and have a decidable first-order theory. Instead the intricacies of Boolean algebra are divided between the structure of infinite algebras and the algorithmic complexity of their syntactic structure. ==Definition== Boolean algebra treats the equational theory of the maximal two-element finitary algebra, called the Boolean prototype, and the models of that theory, called Boolean algebras. These terms are defined as follows. An algebra is a family of operations on a set, called the underlying set of the algebra. We take the underlying set of the Boolean prototype to be . An algebra is finitary when each of its operations takes only finitely many arguments. For the prototype each argument of an operation is either 0 or 1, as is the result of the operation. The maximal such algebra consists of all finitary operations on . The number of arguments taken by each operation is called the arity of the operation. An operation on of arity ''n'', or ''n''-ary operation, can be applied to any of 2''n'' possible values for its ''n'' arguments. For each choice of arguments the operation may return 0 or 1, whence there are 22''n'' ''n''-ary operations. The prototype therefore has two operations taking no arguments, called zeroary or nullary operations, namely zero and one. It has four unary operations, two of which are constant operations, another is the identity, and the most commonly used one, called ''negation'', returns the opposite of its argument: 1 if 0, 0 if 1. It has sixteen binary operations; again two of these are constant, another returns its first argument, yet another returns its second, one is called ''conjunction'' and returns 1 if both arguments are 1 and otherwise 0, another is called ''disjunction'' and returns 0 if both arguments are 0 and otherwise 1, and so on. The number of (''n''+1)-ary operations in the prototype is the square of the number of ''n''-ary operations, so there are 162 = 256 ternary operations, 2562 = 65,536 quaternary operations, and so on. A family is indexed by an index set. In the case of a family of operations forming an algebra, the indices are called operation symbols, constituting the language of that algebra. The operation indexed by each symbol is called the denotation or interpretation of that symbol. Each operation symbol specifies the arity of its interpretation, whence all possible interpretations of a symbol have the same arity. In general it is possible for an algebra to interpret distinct symbols with the same operation, but this is not the case for the prototype, whose symbols are in one-one correspondence with its operations. The prototype therefore has 22''n'' ''n''-ary operation symbols, called the Boolean operation symbols and forming the language of Boolean algebra. Only a few operations have conventional symbols, such as ¬ for negation, ∧ for conjunction, and ∨ for disjunction. It is convenient to consider the ''i''-th ''n''-ary symbol to be ''n''''f''''i'' as done below in the section on truth tables. An equational theory in a given language consists of equations between terms built up from variables using symbols of that language. Typical equations in the language of Boolean algebra are ''x''∧''y'' = ''y''∧''x'', ''x''∧''x'' = ''x'', ''x''∧¬''x'' = ''y''∧¬''y'', and ''x''∧''y'' = ''x''. An algebra satisfies an equation when the equation holds for all possible values of its variables in that algebra when the operation symbols are interpreted as specified by that algebra. The laws of Boolean algebra are the equations in the language of Boolean algebra satisfied by the prototype. The first three of the above examples are Boolean laws, but not the fourth since 1∧0 ≠ 1. The equational theory of an algebra is the set of all equations satisfied by the algebra. The laws of Boolean algebra therefore constitute the equational theory of the Boolean prototype. A model of a theory is an algebra interpreting the operation symbols in the language of the theory and satisfying the equations of the theory. :''A Boolean algebra is any model of the laws of Boolean algebra.'' That is, a Boolean algebra is a set and a family of operations thereon interpreting the Boolean operation symbols and satisfying the same laws as the Boolean prototype. If we define a homologue of an algebra to be a model of the equational theory of that algebra, then a Boolean algebra can be defined as any homologue of the prototype. Example 1. The Boolean prototype is a Boolean algebra, since trivially it satisfies its own laws. It is thus the prototypical Boolean algebra. We did not call it that initially in order to avoid any appearance of circularity in the definition. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Boolean algebras canonically defined」の詳細全文を読む スポンサード リンク
|